// https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence/description/

// 算法思路总结：
// 1. 使用动态规划寻找最长斐波那契子序列
// 2. dp[i][j]表示以arr[i]、arr[j]结尾的斐波那契序列长度
// 3. 哈希表记录数值到索引的映射，快速查找前驱元素
// 4. 时间复杂度：O(n²)，空间复杂度：O(n²)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <unordered_map>

class Solution 
{
public:
    int lenLongestFibSubseq(vector<int>& arr) 
    {
        int m = arr.size();
        if (m < 3) return 0;

        vector<vector<int>> dp(m, vector<int>(m, 2));
        unordered_map<int, int> up;
        int ret = 2;
        
        for (int i = 0 ; i < m - 1 ; i++)
        {
            for (int j = i + 1 ; j < m ; j++)
            {
                int a = arr[j] - arr[i];
                if (up.count(a))
                {
                    dp[i][j] = dp[up[a]][i] + 1;
                }
                ret = max(ret, dp[i][j]);
            }
            up[arr[i]] = i;
        }
        return ret < 3 ? 0 : ret;
    }   
};

int main()
{
    vector<int> v1 = {1,2,3,4,5,6,7,8}, v2 = {1,3,7,11,12,14,18};
    Solution sol;

    cout << sol.lenLongestFibSubseq(v1) << endl;
    cout << sol.lenLongestFibSubseq(v2) << endl;

    return 0;
}